class Solution {
public:
    bool row[9][10];
    bool col[9][10];
    bool arr[3][3][10];
    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0;i < 9;i++)
        {
            for (int j = 0;j < 9;j++)
            {
                if (board[i][j] != '.')
                {
                    row[i][board[i][j] - '0'] = true;col[j][board[i][j] - '0'] = true;arr[i / 3][j / 3][board[i][j] - '0'] = true;
                }
            }
        }
        dfs(board);
        return;
    }
    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0;i < 9;i++)
        {
            for (int j = 0;j < 9;j++)
            {
                if (board[i][j] == '.')
                {
                    for (int n = 1;n <= 9;n++)
                    {
                        if (row[i][n] == false && col[j][n] == false && arr[i / 3][j / 3][n] == false)
                        {
                            board[i][j] = n + '0';
                            row[i][n] = true;col[j][n] = true;arr[i / 3][j / 3][n] = true;
                            bool flag = dfs(board);
                            if (flag == false)
                            {
                                board[i][j] = '.';
                                row[i][n] = false;col[j][n] = false;arr[i / 3][j / 3][n] = false;

                            }
                            else break;


                        }
                    }
                    if (board[i][j] == '.')
                        return false;
                    else return true;

                }
            }
        }

        return true;
    }
};